package com.example.Arithmetic.Lettcode;

import org.junit.jupiter.api.Test;

/**
 * 日期：2023/12/28
 * 时间：21:45
 * 描述:寻找与上一个数的最大差值
 * 内部类做令牌桶，寻找最大值和最小值
 */
public class E01Lettcode164_3 {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        // 2. 桶排序
        int max = nums[0];
        int min = nums[0];
//        寻找最大值和最小值
        for (int i1 = 1; i1 < nums.length; i1++) {
            if (nums[i1] > max) {
                max = nums[i1];
            }
            if (nums[i1] < min) {
                min = nums[i1];
            }
        }
        int range = Math.max(1, (max - min) / nums.length);
        Pair[] pairs = new Pair[(max - min) / range + 1];

//        放入数据
        for (int n : nums) {
            int idx = (n - min) / range;
            if (pairs[idx] == null) {
                pairs[idx] = new Pair();
            }
            pairs[idx].add(n);
        }
//        寻找最大值
        max = 0;
        int lastMax = pairs[0].max;
        for (int i = 1; i < pairs.length; i++) {
            Pair pair = pairs[i];
            if (pair != null) {
                max=Math.max(max,pair.min-lastMax);
                lastMax=pair.max;
            }
        }
        return max;
    }

    static class Pair {
        int max = 0;
        int min = 1000_000_000;

        public void add(int v) {
            max = Math.max(v, max);
            min = Math.min(min, v);
        }
    }

    @Test
    public  void main() {
        int[] arr1 = new int[]{10000000, 1};
        E01Lettcode164_3 e01Lettcode164 = new E01Lettcode164_3();
        int i = e01Lettcode164.maximumGap(arr1);
        System.out.println(i);
    }
}

